package ai.zixing.mashibing.advance_class.first.class01;

import sun.text.normalizer.UBiDiProps;

import java.util.LinkedList;

/**
 * 给定一个整型数组arr，和一个整数num
 * 某个arr中的子数组sub，如果想达标，必须满足：
 * sub中最大值 – sub中最小值 <= num，
 * 返回arr中达标子数组的数量
 */
public class Code02_AllLessNumSubArray {

    // O(N)
    public static int getNum1(int[] arr, int num) {
        // base case
        if (arr == null || arr.length == 0) {
            return 0;
        }
        // 窗口内最大值队列
        LinkedList<Integer> maxQ = new LinkedList<>();
        // 窗口内最小值队列
        LinkedList<Integer> minQ = new LinkedList<>();
        int L = 0;
        int R = 0;
        // 左闭右开
        int res = 0;
        // L 开始，尝试每一个元素开头
        while (L < arr.length) {
            // 窗口开头为 L， R 扩展到违规为止
            while (R < arr.length) {
                // 一定要放在比当前值小的后面
                while (!minQ.isEmpty() && arr[minQ.peekFirst()] >= arr[R]) {
                    minQ.pollLast();
                }
                minQ.addLast(R);
                // 窗口内最大值
                while (!maxQ.isEmpty() && arr[maxQ.peekFirst()] <= arr[R]) {
                    maxQ.pollLast();
                }
                maxQ.addLast(R);
                // 不达标了，break
                if (arr[maxQ.getFirst()] - arr[minQ.getFirst()] < num) {
                    break;
                }
                R++;
            }
            // R 是最后一个达标的
            res += R - L;
            // L 位置是否过期
            if (minQ.peekFirst() == L) {
                minQ.pollFirst();
            }
            if (maxQ.pollFirst() == L) {
                maxQ.pollFirst();
            }
            L++;
        }
        return res;
    }
}
